// 2025/3/2
// https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked
// 和为k的子数组

// 自己写的，冗余很多
class Solution {
    public:
        int subarraySum(vector<int>& nums, int k) {
            int n = nums.size();
            vector<int> prev(n + 1, 0);
            unordered_multimap<int, int> hash;
            for(int i = 1; i < n + 1; i++)
            {
                prev[i] = prev[i - 1] + nums[i - 1];
                hash.emplace(prev[i], i);
            }
    
            int ans = 0;
            for(int i = 1; i < n + 1; i++)
            {
                auto it = hash.equal_range(prev[i - 1] + k);
                while(it.first != it.second)
                {
                    if(it.first->second >= i)
                        ans++;
                    ++(it.first);
                }
            }
    
            return ans;
        }
    };

// 官方解答
class Solution {
    public:
        int subarraySum(vector<int>& nums, int k) {
            int n = nums.size(), ans = 0, pre = 0;
            unordered_map<int, int> hash;
            hash[0] = 1;
            for(auto& e : nums)
            {
                pre += e;
                if(hash.find(pre - k) != hash.end())
                {
                    ans += hash[pre - k];
                }
                ++hash[pre];
            }
    
            return ans;
        }
    };